package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(rob([]int{2, 7, 9, 3, 1}))
}

func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	if len(nums) == 2 {
		return int(math.Max(float64(nums[0]), float64(nums[1])))
	}
	dpTab := make([]int, 3)
	dpTab[0] = nums[0]
	dpTab[1] = nums[1]
	dpTab[2] = nums[0] + nums[2]
	for i := 3; i < len(nums); i++ {
		dpTab[i%3] = int(math.Max(float64(dpTab[(i-2)%3]), float64(dpTab[(i-3)%3]))) + nums[i]
	}
	return int(math.Max(float64(dpTab[(len(nums)-1)%3]), float64(dpTab[(len(nums)-2)%3])))
}
